<?php
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val)
    {
        $this->val = $val;
    }
}

class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function mergeTwoLists($l1, $l2) {
        $pre_head  = new ListNode(-1);
        $prev = $pre_head;

        while ($l1 != null && $l2 != null) {
            if ($l1->val <= $l2->val) {
                $prev->next = $l1;
                $l1 = $l1->next;
            } else {
                $prev->next = $l2;
                $l2 = $l2->next;
            }
            $prev = $prev->next;
        }

        if ($l1 || $l2) {
            $prev->next = $l1 == null ? $l2 : $l1;
        }

        return $pre_head->next;
    }
}